package com.sicheng.lc.lc笔试;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/11 22:36
 */
public class 质因子 {

    /**
     *
     * 此题用C++写最好，因为IO次数太大
     * 给定整数K和一个数组A，现需要在A中寻找子数组，
     * 使其包含整数K的所有质因子，相同数字要求收集足够个数。
     * 请输出满足条件的最小子数组长度（如果没有满足条件的子数组，输出0即可）。
     * 输入T，代表T组数据。（T<=5）
     * 每组数据输入k和n（k<1e6, n<5e5），n为数组长度。然后输入n个整数。(a[i]<2147483647)
     * 对于每组数据，输出满足条件的最小子数组长度
     * <p>
     * input:
     * 2
     * 20 8
     * 1 2 3 2 6 5 2 1
     * 17 10
     * 1 4 5 7 10 8 7 17 2 8
     * output:
     * 4
     * 1
     */
    static int N = (int) 1e5 * 5;
    static int[] a = new int[N];
    static Map<Integer, Integer> f(int x) {
        HashMap<Integer, Integer> map = new HashMap<>(1 << 6);
        for (int i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                x /= i;
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
        }
        if (x > 1)
            map.put(x, map.getOrDefault(x, 0) + 1);
        return map;
    }

    static int MAX = Integer.MAX_VALUE >> 2;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int k, n, min = MAX;
        for (int m = 0; m < t; m++) {
            k = sc.nextInt();
            n = sc.nextInt();
            Map<Integer, Integer> map = f(k);
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            for (int j = 0, i = 0; j < n; j++) {
                if (map.containsKey(a[j])) {
                    map.put(a[j], map.get(a[j]) - 1);
                }
                while (i <= j && check(map)) {
                    min = Math.min(min, j - i + 1);
                    if (map.containsKey(a[i]))
                        map.put(a[i], map.get(a[i]) + 1);
                    i++;
                }
            }
            System.out.println(min == MAX ? 0 : min);
        }
    }

    private static boolean check(Map<Integer, Integer> map) {
        for (int x : map.values()) {
            if (x > 0)
                return false;
        }
        return true;
    }


}
